package com.liu.algorithm.sort;

import java.util.Arrays;

/**
 * @author LiuZhiYong
 * @description 选择排序
 * @date 2022-10-18
 **/
public class Code01SelectionSort {

    /**
     * 选择排序
     * 思路:
     *      1. 设置数组最小元素的下标minIndex为第一个元素, 选取数组第一个元素, 依次和后面的元素对比, 如果当前元素小于后续的元素则将小的元素的下标赋值给minIndex
     *      2. 调换当前元素与minIndex下标元素的位置
     *      3. 第一轮比较完成之后, 由第二个元素开始进行第二轮比较...
     *  N个元素数组排序流程:
     *      1. 第0号元素  比较 n-1 次 --> 调换位置O(1)
     *      2. 第1号元素  比较 n-2 次 --> 调换位置O(1)
     *      3. 第2号元素  比较 n-3 次 --> 调换位置O(1)
     *      4. 第3号元素  比较 n-4 次 --> 调换位置O(1)
     *      ...
     *      n-2. 第n-2号元素 比较n-(n-1)次 --> 调换位置O(1)
     *
     *      等差数列求和公式: Sn = n * a1 + n(n-1)d/2
     *      表达式 --> aN^2 + bN + c + N --> aN^2 + bN + c  a、b、c为常数
     *      取最忽略掉系数的高阶项 N^2
     *      时间复杂度O(n^2)
     *
     * @param arr   待排序数组
     * @author liuzhiyong
     * @date 2022/10/18
     */
    public static void selectionSort(int[] arr) {
        if (null == arr || arr.length < 2) {
            System.out.println("传入的数组不需要排序!");
            return;
        }
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    minIndex = j;
                }
            }
            // 调换位置
            swap(arr, i, minIndex);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * i 和 j 位置上的元素调换位置
     *
     * @param arr   数组
     * @param i     下标i
     * @param j     下标j
     * @author liuzhiyong
     * @date 2022/10/18
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5,5,4,4,3, 2, 1};
        selectionSort(arr);
    }

}